{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 排序算法\n",
    "\n",
    "## 1、冒泡排序（Bubble Sort）\n",
    "\n",
    "### 1.1、简介\n",
    "\n",
    "冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们两个的顺序错误就把它们两个交换。走访数列的工作是重复的，直到最后没有再需要交换，也就是说该数列已经排序完成了。这个算法的名字由来是因为越小的元素会经由交换慢慢 \"浮\" 到数列的顶端。\n",
    "\n",
    "### 1.2、算法描述\n",
    "\n",
    " - 比较相邻的元素。如果第一个比第二个大，就交换它们两个；\n",
    " - 对每一组相邻元素做相同的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；\n",
    " - 针对所有的元素重复以上的步骤，除了最后一个；\n",
    " - 重复步骤 1~3 ，直到排序完成。\n",
    " \n",
    "### 1.3、动图演示\n",
    "\n",
    "![](/images/SortingAlgorithm/BubbleSort_1.gif)\n",
    "\n",
    "### 1.4、代码实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 5, 7, 9]\n"
     ]
    }
   ],
   "source": [
    "def bubble_sort(nums):\n",
    "    # 外层循环负责设置冒泡排序进行的次数\n",
    "    for i in range(len(nums)-1):\n",
    "        # 内层循环负责前后两两比较，求最大值放到最后\n",
    "        # j 为列表下标\n",
    "        for j in range(len(nums)-1-i):\n",
    "            # 如果相互比较的两个数，前一个数比后一个数大\n",
    "            if nums[j] > nums[j+1]:\n",
    "                nums[j], nums[j+1] = nums[j+1], nums[j]\n",
    "    return nums\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = [5, 1, 9, 3, 2, 7]\n",
    "    bubble_sort(nums)\n",
    "    print(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5、代码优化\n",
    "\n",
    "#### 1.5.1、优化 1\n",
    "\n",
    "如果上面代码中，里面一层循环在某次扫描中没有执行交换，则说明此时数组已经全部有序了，无需再进行扫描。因此，我们增加一个标记，每次发生交换，用来标记，如果某次循环完没有标记，则说明已经完成排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 5, 7, 9]\n"
     ]
    }
   ],
   "source": [
    "# 改进版的冒泡排序_1\n",
    "def bubble_sort_2(nums):\n",
    "    # 外层循环负责设置冒泡排序进行的次数\n",
    "    for i in range(len(nums)-1):\n",
    "        # 标记是否已经完成排序\n",
    "        swaped = False\n",
    "        # 内层循环负责前后两两比较，求最大值放到最后，j 为列表下标\n",
    "        for j in range(len(nums)-1-i):\n",
    "            # 如果相互比较的两个数，前一个数比后一个数大\n",
    "            if nums[j] > nums[j+1]:\n",
    "                nums[j], nums[j+1] = nums[j+1], nums[j]\n",
    "                swaped = True\n",
    "        # 如果上一次扫描没有发生交换，说明数组已经全部都排好序了，那我们就退出循环\n",
    "        if not swaped:\n",
    "            break\n",
    "    return nums\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = [5, 1, 9, 3, 2, 7]\n",
    "    bubble_sort_2(nums)\n",
    "    print(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### 1.5.2、优化 2\n",
    "\n",
    "在我们第一步优化的基础上，我们可以进一步思考：如果 R[0 ~ i] 已是有序区间，上次扫描的区间是 R[i ~ n]，记上次扫描时最后一次执行交换的位置为 lastSwapPos，则 lastSwapPos 在 i 与 n 之间，不难发现 R[i ~ lastSwapPos] 区间也是有序的，否则这个区间也会发生变换；所以下次扫描区间就可以由 R[i ~ n] 缩减到 R[lastSwapPos ~ n] 。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 5, 7, 9]\n"
     ]
    }
   ],
   "source": [
    "# 改进版的冒泡排序_2\n",
    "def bubble_sort_3(nums):\n",
    "    lastSwapPos = 0\n",
    "    lastSwapPosTemp = 0\n",
    "    # 外层循环负责设置冒泡排序进行的次数\n",
    "    for i in range(len(nums)-1):\n",
    "        lastSwapPos = lastSwapPosTemp\n",
    "        # 内层循环负责前后两两比较，求最大值放到最后，j 为列表下标\n",
    "        for j in range(len(nums)-1-i):\n",
    "            # 如果相互比较的两个数，前一个数比后一个数大\n",
    "            if nums[j] > nums[j+1]:\n",
    "                nums[j], nums[j+1] = nums[j+1], nums[j]\n",
    "                # 记录最后一次发生交换的位置\n",
    "                lastSwapPosTemp = j\n",
    "        # 如果上一次扫描没有发生交换，说明数组已经全部都排好序了，那我们就退出循环\n",
    "        if lastSwapPos == lastSwapPosTemp:\n",
    "            break\n",
    "    return nums\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = [5, 1, 9, 3, 2, 7]\n",
    "    bubble_sort_3(nums)\n",
    "    print(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2、插入排序（Insert Sort）\n",
    "\n",
    "### 2.1、简介\n",
    "\n",
    "插入排序（insert sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。\n",
    "\n",
    "### 2.2、算法描述\n",
    "\n",
    "一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：\n",
    "\n",
    " - 从第一个元素开始，该元素可以认为已经被排序；\n",
    " - 取出下一个元素，在已经排序的元素序列中从后向前扫描；\n",
    " - 如果该元素（已排序）大于新元素，将该元素移到下一个位置；\n",
    " - 重复步骤 3 ，直到找到已排序的元素小于或者等于新元素的位置；\n",
    " - 将新元素插入到该位置后；\n",
    " - 重复步骤 2 ~ 5\n",
    " \n",
    "### 2.3、动图演示\n",
    "\n",
    "![](/images/SortingAlgorithm/InsertSort_1.gif)\n",
    "\n",
    "### 2.4、代码实现\n",
    "\n",
    "插入排序和冒泡排序的区别在于：\n",
    "\n",
    " - 插入排序的前提是：左边是有序的数列\n",
    " - 冒泡排序：相邻的值进行交换，一共进行 n 次"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 1, 9, 3, 2, 7]\n",
      "[5]\n",
      "[1, 5]\n",
      "[1, 5, 9]\n",
      "[1, 3, 5, 9]\n",
      "[1, 2, 3, 5, 9]\n",
      "result: [1, 2, 3, 5, 7, 9]\n"
     ]
    }
   ],
   "source": [
    "def insert_sort(nums):\n",
    "    # 循环  除第一个数字组成的有序数组 以外的数字\n",
    "    for i in range(1, len(nums)):\n",
    "        # 每一个数字，依次和有序数组进行比较\n",
    "        print(nums[:i])\n",
    "        for j in range(len(nums[:i])):\n",
    "            if nums[i] < nums[j]:\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "                \n",
    "if __name__ == \"__main__\":\n",
    "    l = [5, 1, 9, 3, 2, 7]\n",
    "    print(l)\n",
    "    insert_sort(l)\n",
    "    print(\"result: \" + str(l))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3、选择排序（SelectionSort）\n",
    "\n",
    "### 3.1、简介\n",
    "\n",
    "选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 \n",
    "\n",
    "### 3.2、算法描述\n",
    "\n",
    "n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：\n",
    "\n",
    " - 初始状态：无序区为 R[1 ... n]，有序区为空；\n",
    " - 第 i 趟排序 (i = 1, 2, 3, ... n-1) 开始时，当前有序区和无序区分别为 R[1 ... i-1] 和 R[i ... n]。该趟排序从当前无序区中 —— 选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R 交换，使 R[1 ... i] 和 R[i+1 ... n] 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区；\n",
    " - n-1 趟结束，数组有序化了。\n",
    " \n",
    "### 3.3、动图演示\n",
    "\n",
    "![](/images/SortingAlgorithm/SelectionSort_1.gif)\n",
    "\n",
    "### 3.4、代码实现\n",
    "\n",
    "选择排序和冒泡排序的区别在于：\n",
    "\n",
    "选择排序的前提是：找到最大值的位置，最后才进行 1 次交换；\n",
    "而冒泡排序是：相邻的值进行交换，一共进行 n 次交换"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 1, 9, 3, 2, 7]\n",
      "1 [5, 1, 7, 3, 2, 9]\n",
      "2 [5, 1, 2, 3, 7, 9]\n",
      "3 [3, 1, 2, 5, 7, 9]\n",
      "4 [2, 1, 3, 5, 7, 9]\n",
      "5 [1, 2, 3, 5, 7, 9]\n",
      "result: [1, 2, 3, 5, 7, 9]\n"
     ]
    }
   ],
   "source": [
    "def selection_sort(nums):\n",
    "    length = len(nums) - 1\n",
    "\n",
    "    while length:\n",
    "        index = length\n",
    "        # 第一个数字，和后面每一个数字进行对比，找出最大值，放到最后！！\n",
    "        for j in range(length):\n",
    "            if nums[j] > nums[index]:\n",
    "                index = j\n",
    "        nums[length], nums[index] = nums[index], nums[length]\n",
    "        print(len(nums) - length, nums)\n",
    "        length -= 1\n",
    "        \n",
    "if __name__ == \"__main__\":\n",
    "    nums = [5, 1, 9, 3, 2, 7]\n",
    "    print(nums)\n",
    "    selection_sort(nums)\n",
    "    print(\"result: \" + str(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4、快速排序（Quick Sort）\n",
    "\n",
    "### 4.1、简介\n",
    "\n",
    "快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。\n",
    "\n",
    "### 4.2、算法描述\n",
    "\n",
    "快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：\n",
    "\n",
    " - 从数列中挑出一个元素，称为 \"基准\"（pivot）\n",
    " - 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出后，该基准就处于数列的中间位置。这个称为分区（partition）操作；\n",
    " - 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。\n",
    " \n",
    "### 4.3、动图演示\n",
    "\n",
    "![](/images/SortingAlgorithm/QuickSort_1.gif)\n",
    "\n",
    "### 4.4、代码实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 7 ******************************\n",
      "5 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
      "5 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
      "5 9 ******************************\n",
      "5 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
      "2 3 ******************************\n",
      "2 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
      "9 7 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
      "[1, 2, 3, 5, 7, 9]\n"
     ]
    }
   ],
   "source": [
    "def quick_sort(nums, start, end):\n",
    "    i = start\n",
    "    j = end\n",
    "    # 结束排序\n",
    "    if i >= j:\n",
    "        return\n",
    "    # 保存首个数值\n",
    "    key = nums[i]\n",
    "    # 一次排序，i和j的值不断的靠拢，然后最终停止，结束一次排序\n",
    "    while i < j:\n",
    "        # 和最右边的比较，如果值 >=key,然后j-1，慢慢的和前一个值比较;如果值<key，那么就交换位置\n",
    "        # 将 key 作为基准，将小于 key 的值放在左边，将 大于 key 的值放在右边\n",
    "        while i < j and key <= nums[j]:\n",
    "            print(key, nums[j], '*' * 30)\n",
    "            j -= 1\n",
    "        nums[i] = nums[j]\n",
    "        # 交换位置后，然后再和最左边的值开始比较，如果值 <=key,然后i+1，慢慢的和后一个值比较;如果值>key，那么就交换位置\n",
    "        while i < j and key >= nums[i]:\n",
    "            print(key, nums[i], '%' * 30)\n",
    "            i += 1\n",
    "        nums[j] = nums[i]\n",
    "    nums[i] = key\n",
    "    # 左边排序\n",
    "    quick_sort(nums, start, j-1)\n",
    "    # 右边排序\n",
    "    quick_sort(nums, i+1, end)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    l = [5, 1, 9, 3, 2, 7]\n",
    "    quick_sort(l, 0, len(l) - 1)\n",
    "    print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5、希尔排序（ShellSort）\n",
    "\n",
    "### 5.1、简介\n",
    "\n",
    "希尔排序（Shell Sort）也是插入排序的一种。也称为缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。\n",
    "\n",
    "1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会 **优先比较距离较远的元素。希尔排序又叫缩小增量排序。**\n",
    "\n",
    "### 5.2、算法描述\n",
    "\n",
    "先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：\n",
    "\n",
    " - 选择一个增量序列 $t_1, t_2, …, t_k$ ，其中 $t_i>t_j, t_k=1$ ；\n",
    " - 按增量序列个数 k，对序列进行 k 趟排序；\n",
    " - 每趟排序，根据对应的增量 $t_i$，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。\n",
    " \n",
    "**补充描述：**\n",
    " \n",
    "是不是有些不明白呢？那我们用通俗一些的语句来说。\n",
    "\n",
    "直接插入排序在在本身数量比较少的时候情况下效率很高，如果待排数的数量很多，其效率不是很理想。\n",
    "\n",
    "　　回想一下直接插入排序过程，排序过程中，我们可以设置一条线，左边是排好序的，右边则是一个一个等待排序，\n",
    "\n",
    "如果最小的那个值在最右边，那么排这个最小值的时候，需要将所有元素向右边移动一位。\n",
    "\n",
    "　　是否能够减少这样的移位呢？\n",
    "\n",
    "　　我们不希望它是一步一步的移动，而是大步大步的移动。希尔排序就被发明出来了，它也是当时打破效率\n",
    "\n",
    "O（n2）的算法之一。希尔排序算法通过设置一个间隔，对同样间隔的数的集合进行插入排序，此数集合中的元素\n",
    "\n",
    "移位的长度是以间隔的长度为准，这样就实现了大步位移。但是最后需要对元素集合进行一次直接插入排序，所以\n",
    "\n",
    "最后的间隔一定是1。\n",
    "\n",
    "下面举一个例子：\n",
    "\n",
    "第一趟希尔排序，间隔为4\n",
    "\n",
    "![](/images/SortingAlgorithm/ShellSort_2.png)\n",
    "\n",
    "第二趟排序：间隔为 2\n",
    "\n",
    "![](/images/SortingAlgorithm/ShellSort_3.png)\n",
    "\n",
    "第三趟排序，间隔为 1，即 直接插入排序法（InsertSort）：\n",
    "\n",
    "具体的插入排序过程，这里我们就不再详细说了。\n",
    "\n",
    "```\n",
    "减小间隔：\n",
    "\n",
    "上面已经演示了以4为初始间隔对包含10个数据项的数组进行排序的情况。对于更大的数组开始的间隔也应该更大。然后间隔不断减小，直到间隔变成1。\n",
    "\n",
    "举例来说，含有1000个数据项的数组可能先以364为增量，然后以121为增量，以40为增量，以13为增量，以4为增量，最后以 1为增量进行希尔排序。用来形成间隔的数列被称为间隔序列。这里所表示的间隔序列由Knuth提出，此序列是很常用的。数列以逆向形式从1开始，通过递归表达式\n",
    "\n",
    "h = 3 * b + 1\n",
    "\n",
    "来产生，初始值为 1 。\n",
    "\n",
    "在排序算法中，首先在一个短小的循环中使用序列的生成公式来计算出最初的间隔。h值最初被赋为1，然后应用公式h=3*h+1生成序列1,4,13,40,121,364，等等。当间隔大于数组大小的时候，这个过程停止。对于一个含有1000个数据项的数组，序列的第七个数字，1093就太大了。因此，使用序列的第六个数字作为最大的数字来开始这个排序过程，作364-增量排序。然后，每完成一次排序全程的外部循环，用前面提供的此公式倒推式来减小间隔：\n",
    "\n",
    "h=(h-1)/3\n",
    "\n",
    "这个倒推的公式生成逆置的序列364,121,40,13,4,1。从364开始，以每一个数字作为增量进行排序。当数组用1-增量排序后，算法结束。\n",
    "\n",
    "希尔排序比插入排序快很多，它是基于什么原因呢？当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长。这是非常有效率的。当h减小时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。\n",
    "\n",
    "注意后期的排序过程不撤销前期排序所做的工作。例如，已经完成了以40-增量的排序的数组，在经过以13-增量的排序后仍然保持了以40-增量的排序的结果。如果不是这样的话，希尔排序就无法实现排序的目的。\n",
    "```\n",
    " \n",
    "### 5.3、动图演示\n",
    "\n",
    "![](/images/SortingAlgorithm/ShellSort_1.gif)\n",
    "\n",
    "再附加一个静态图：\n",
    "\n",
    "![](/images/SortingAlgorithm/ShellSort_4.png)\n",
    "\n",
    "### 5.4、代码实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "开始 [5, 2, 9, 8, 1, 10, 3, 4, 7]\n",
      "3 -- [3, 2, 9, 5, 1, 10, 8, 4, 7]\n",
      "3 -- [3, 1, 9, 5, 2, 10, 8, 4, 7]\n",
      "3 -- [3, 1, 7, 5, 2, 9, 8, 4, 10]\n",
      "2 -- [2, 1, 3, 5, 7, 9, 8, 4, 10]\n",
      "2 -- [2, 1, 3, 4, 7, 5, 8, 9, 10]\n",
      "1 -- [1, 2, 3, 4, 5, 7, 8, 9, 10]\n",
      "结束 [1, 2, 3, 4, 5, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "# 直接插入排序\n",
    "def insert_sort(nums, start, increment):\n",
    "    for i in range(start+increment, len(nums), increment):\n",
    "        for j in range(start, len(nums[:i]), increment):\n",
    "            if nums[i] < nums[j]:\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "    print(increment, '--', nums)\n",
    "    return nums\n",
    "\n",
    "# 希尔排序\n",
    "def shell_sort(nums, increment):\n",
    "    # 依次进行分层\n",
    "    while increment:\n",
    "        # 每一层，都进行n次插入排序\n",
    "        for i in range(0, increment):\n",
    "            insert_sort(nums, i, increment)\n",
    "        increment -= 1\n",
    "    return nums\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    l = [5, 2, 9, 8, 1, 10, 3, 4, 7]\n",
    "    increment = int(len(l)/3)+1 if len(l)%3 else int(len(l)/3)\n",
    "    print(\"开始\", l)\n",
    "    l = shell_sort(l, increment)\n",
    "    print(\"结束\", l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6、归并排序（MergeSort）\n",
    "\n",
    "### 6.1、简介\n",
    "\n",
    "归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。\n",
    "\n",
    "### 6.2、算法描述\n",
    "\n",
    " - 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；\n",
    " - 对这两个子序列分别采用归并排序；\n",
    " - 将两个排序好的子序列合并成一个最终的排序序列。\n",
    " \n",
    "### 6.3、动图演示\n",
    "\n",
    "![](/images/SortingAlgorithm/MergeSort_1.gif)\n",
    "\n",
    "### 6.4、代码实现\n",
    "\n",
    "归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n",
      "********************\n",
      "[2]\n",
      "____________________\n",
      "result: [1, 2]\n",
      "[4]\n",
      "********************\n",
      "[5]\n",
      "____________________\n",
      "result: [4, 5]\n",
      "[3]\n",
      "********************\n",
      "[4, 5]\n",
      "____________________\n",
      "result: [3, 4, 5]\n",
      "[1, 2]\n",
      "********************\n",
      "[3, 4, 5]\n",
      "____________________\n",
      "result: [1, 2, 3, 4, 5]\n",
      "[7]\n",
      "********************\n",
      "[90]\n",
      "____________________\n",
      "result: [7, 90]\n",
      "[6]\n",
      "********************\n",
      "[7, 90]\n",
      "____________________\n",
      "result: [6, 7, 90]\n",
      "[23]\n",
      "********************\n",
      "[45]\n",
      "____________________\n",
      "result: [23, 45]\n",
      "[21]\n",
      "********************\n",
      "[23, 45]\n",
      "____________________\n",
      "result: [21, 23, 45]\n",
      "[6, 7, 90]\n",
      "********************\n",
      "[21, 23, 45]\n",
      "____________________\n",
      "result: [6, 7, 21, 23, 45, 90]\n",
      "[1, 2, 3, 4, 5]\n",
      "********************\n",
      "[6, 7, 21, 23, 45, 90]\n",
      "____________________\n",
      "result: [1, 2, 3, 4, 5, 6, 7, 21, 23, 45, 90]\n",
      "[1, 2, 3, 4, 5, 6, 7, 21, 23, 45, 90]\n"
     ]
    }
   ],
   "source": [
    "def MergeSort(lists):\n",
    "    if len(lists) <= 1:\n",
    "        return lists\n",
    "    num = int(len(lists) / 2)\n",
    "    # 从中间，进行数据的拆分, 递归的返回数据进行迭代排序\n",
    "    left = MergeSort(lists[:num])\n",
    "    right = MergeSort(lists[num:])\n",
    "    print(left)\n",
    "    print(\"*\" * 20)\n",
    "    print(right)\n",
    "    print(\"_\" * 20)\n",
    "    return Merge(left, right)\n",
    "\n",
    "# 将 2 个已经排好序的子序列合并成一个序列，也就是 2-路归并\n",
    "def Merge(left, right):\n",
    "    r, l = 0, 0\n",
    "    result = []\n",
    "    # 这里将两个序列中的每个值都比较一下，最小的放到最左边\n",
    "    while l < len(left) and r < len(right):\n",
    "        if left[l] < right[r]:\n",
    "            result.append(left[l])\n",
    "            l += 1\n",
    "        else:\n",
    "            result.append(right[r])\n",
    "            r += 1\n",
    "    result += right[r:]\n",
    "    result += left[l:]\n",
    "    print('result:', result)\n",
    "    # 最终将合并好的完整序列返回\n",
    "    return result\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    print(MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7、基数排序\n",
    "\n",
    "### 7.1、简介\n",
    "\n",
    "以十进制为例，基数指的是数的位，如个位，十位百位等。而以十六进制为例，0xB2，就有两个radices（radix的复数）。\n",
    "\n",
    "基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。\n",
    "\n",
    "### 7.2、算法描述\n",
    "\n",
    " - 取得数组中的最大数，并取得位数；\n",
    " - arr 为原始数组，从最低位开始取每个位组成 radix 数组；\n",
    " - 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）\n",
    " \n",
    "**补充描述：**\n",
    "\n",
    "基数排序不同于其他的排序算法，它不是基于比较的算法。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。它是一种稳定的排序算法。多关键字排序中有两种方法：最高位优先法(MSD)和最低位优先法（LSD）。通常用于对数的排序选择的是最低位优先法，即先对最次位关键字进行排序，再对高一位的关键字进行排序，以此类推。\n",
    "\n",
    "算法的思想：类似于桶式排序，我们需要给待排序记录准备10个桶，为什么是10个？？因为一个数的任何一位上，其数字大小都位于0~9之间，因此采用10个桶，桶的编号分别为0,1,2,3,4...9，对应待排序记录中每个数相应位的数值，基数排序也是因此而得名。我们先根据待排序记录的每个数的个位来决定让其加入哪个桶中。例如：待排序数组为\n",
    "\n",
    "278     109    63    930   589   184   505    269   8    83\n",
    "\n",
    "求取每个数的个位数，依次为：8   9   3  0  9   4  5  9  8  3\n",
    "\n",
    "依照其个位数决定将其加入哪个桶中\n",
    "\n",
    "![](/images/SortingAlgorithm/RadixSort_2.png)\n",
    " \n",
    "### 7.3、动图演示\n",
    "\n",
    "![](/images/SortingAlgorithm/RadixSort_1.gif)\n",
    "\n",
    "### 7.4、代码实现\n",
    "\n",
    "基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要 $O(n)$ 的时间复杂度，而且分配之后得到新的关键字序列又需要 $O(n)$ 的时间复杂度。假如待排数据可以分为 $d$ 个关键字，则基数排序的时间复杂度将是 $O(d*2n)$ ，当然 $d$ 要远远小于 $n$ ，因此基本上还是线性级别的。\n",
    "\n",
    "基数排序的空间复杂度为 $O(n+k)$ ，其中 $k$ 为桶的数量。一般来说 $n>>k$ ，因此额外空间需要大概 $n$ 个左右。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 5, 7, 9]\n"
     ]
    }
   ],
   "source": [
    "# ************************基数排序****************************\n",
    "# 确定排序的次数\n",
    "# 排序的顺序跟序列中最大数的位数相关\n",
    "def radix_sort_nums(L):\n",
    "    maxNum = L[0]\n",
    "    #寻找序列中的最大数\n",
    "    for x in L:\n",
    "        if maxNum < x:\n",
    "            maxNum = x\n",
    "    # 确定序列中的最大元素的位数\n",
    "    times = 0\n",
    "    while (maxNum > 0):\n",
    "        maxNum = int((maxNum/10))\n",
    "        times += 1\n",
    "    return times\n",
    "\n",
    "# 找到num从低到高第pos位的数据\n",
    "def get_num_pos(num, pos):\n",
    "    return (int((num/(10**(pos-1))))) % 10\n",
    "\n",
    "# 基数排序\n",
    "def radix_sort(L):\n",
    "    count = 10 * [None]       # 存放各个桶的数据统计个数\n",
    "    bucket = len(L) * [None]  # 暂时存放排序结果\n",
    "    # 从低位到高位依次执行循环\n",
    "    for pos in range(1, radix_sort_nums(L)+1):\n",
    "        # 置空各个桶的数据统计\n",
    "        for x in range(0, 10):\n",
    "            count[x] = 0\n",
    "        # 统计当前该位(个位，十位，百位....)的元素数目\n",
    "        for x in range(0, len(L)):\n",
    "            # 统计各个桶将要装进去的元素个数\n",
    "            j = get_num_pos(int(L[x]), pos)\n",
    "            count[j] += 1\n",
    "        # count[i]表示第i个桶的右边界索引\n",
    "        for x in range(1,10):\n",
    "            count[x] += count[x-1]\n",
    "        # 将数据依次装入桶中\n",
    "        for x in range(len(L)-1, -1, -1):\n",
    "            # 求出元素第K位的数字\n",
    "            j = get_num_pos(L[x], pos)\n",
    "            # 放入对应的桶中，count[j]-1是第j个桶的右边界索引\n",
    "            bucket[count[j]-1] = L[x]\n",
    "            # 对应桶的装入数据索引-1\n",
    "            count[j] -= 1\n",
    "        # 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表\n",
    "        for x in range(0, len(L)):\n",
    "            L[x] = bucket[x]\n",
    "            \n",
    "if __name__ == \"__main__\":\n",
    "    l = [5, 1, 9, 3, 2, 7]\n",
    "    radix_sort(l)\n",
    "    print(l)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
